package others.yuan.jin.sort;

/**
 * For any element, i, in a list of size n, the following is true:
 *    -Parent element index = i/2 (floor(i))
 *    -Left child element index = 2i
 *    -Right child element index = 2i + 1
 */

/**
 * A Java implementation of the heap sorting algorithm. This version uses an
 * array to represent the heap. Uses a binary representation of the number of
 * elements currently in the heap to find the pathway to the next
 * insertion/removal site.
 * 
 * http://www.dreamincode.net/code/snippet2444.htm
 * 
 * http://rosettacode.org/wiki/Sorting_algorithms/Heapsort#Java
 * 
 * @author Yuan
 * 
 */
class HeapSort {
	public static void heapSort(int[] a) {
		int count = a.length;

		// first place a in max-heap order
		heapify(a, count);

		int end = count - 1;
		while (end > 0) {
			// swap the root(maximum value) of the heap with the
			// last element of the heap
			int tmp = a[end];
			a[end] = a[0];
			a[0] = tmp;
			// put the heap back in max-heap order
			siftDown(a, 0, end - 1);
			// decrement the size of the heap so that the previous
			// max value will stay in its proper place
			end--;
		}
	}

	public static void heapify(int[] a, int count) {
		// start is assigned the index in a of the last parent node
		int start = (count - 2) / 2; // binary heap

		while (start >= 0) {
			// sift down the node at index start to the proper place
			// such that all nodes below the start index are in heap
			// order
			siftDown(a, start, count - 1);
			start--;
		}
		// after sifting down the root all nodes/elements are in heap order
	}

	public static void siftDown(int[] a, int start, int end) {
		// end represents the limit of how far down the heap to sift
		int root = start;

		while ((root * 2 + 1) <= end) { // While the root has at least one child
			int child = root * 2 + 1; // root*2+1 points to the left child
			// if the child has a sibling and the child's value is less than its
			// sibling's...
			if (child + 1 <= end && a[child] < a[child + 1])
				child = child + 1; // ... then point to the right child instead
			if (a[root] < a[child]) { // out of max-heap order
				int tmp = a[root];
				a[root] = a[child];
				a[child] = tmp;
				root = child; // repeat to continue sifting down the child now
			} else
				return;
		}
	}
}
